// 莫比乌斯反演
// 数字表格
// 测试链接 ：https://www.luogu.com.cn/problem/P3704
// 相关帖子 ：https://www.cnblogs.com/dx123/p/16977336.html
// 提交以下的code，可以直接通过

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000001;
const int P = 1e9 + 7;
int cnt;
int mu[MAXN];
int prime[MAXN];
bool visited[MAXN];
int f[MAXN], g[MAXN], F[MAXN];

int quickPow(int a, long long b)
{
    int ans = 1;
    while(b)
    {
        if(b & 1) ans = 1LL * ans * a % P;
        a = 1LL * a * a % P;
        b >>= 1;
    }
    return ans;
}

void init()
{
    mu[1] = 1;
    for(int i = 2; i < MAXN; ++i)
    {
        if(!visited[i])
        {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1; i * prime[j] < MAXN; ++j)
        {
            visited[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
            mu[i * prime[j]] = -mu[i];
        }
    }
    f[1] = g[1] = F[0] = F[1] = 1;
    for(int i = 2; i < MAXN; ++i)
    {
        f[i] = (f[i - 1] + f[i - 2]) % P; // 斐波那契数列
        g[i] = quickPow(f[i], P - 2); // 斐波那契数的逆元
        F[i] = 1;
    }
    for(int i = 1; i < MAXN; ++i)
    {
        for(int j = i; j < MAXN; j += i)
        {
            if(mu[j / i]) F[j] = 1LL * F[j] * (mu[j / i] == 1 ? f[i] : g[i]) % P;
        }
    }
    for(int i = 2; i < MAXN; ++i) F[i] = 1LL * F[i] * F[i - 1] % P; // 前缀积
}

int compute(int n, int m)
{
    if(n > m) swap(n, m);
    int ans = 1;
    for(int l = 1, r, s; l <= n; l = r + 1)
    {
        r = min(n / (n / l), m / (m / l));
        s = 1LL * F[r] * quickPow(F[l - 1], P - 2) % P; // 区间积
        ans = 1LL * ans * quickPow(s, 1LL * (n / l) * (m / l) % (P - 1)) % P;
    }
    return ans;
}

int main()
{
    init();
    int t, n, m;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        printf("%d\n", compute(n, m));
    }

    return 0;
}